Advanced Topics in Computer Science (236603)
Spring semester 2011
Home page of the course: http://www.cs.technion.ac.il/~janos/COURSES/236603-11
last updated: 29.12.2010
Graph polynomials and graph invariants
In 2005-2006 I gave a similar course as a graduate seminar Graph polynomials and graph
decompositions
238900 with
Slides of seminar lectures.
See also lectures
10 and
11 of Logical Methods in Combinatorics
236605-09 given in the Winter Semester 2009/10.
For those students who have already taken 236603 before,
but on another topic, arrangements will be found
to get credit again.
NEW: Projects: Topics and Assignments
UPDATED: Slides and abstracts of the lectures
Mailing List
Lecturer: Prof. J.A. Makowsky
Time: Sunday, 14:30-16:30.
Place: TBA
Prerequisites: The course is rather elementary.
Useful is some knowledge in
elementary graph theory, computability and
some familiarity with linear and abstract algebra.
Format:
Two hours frontal presentations.
Requirements:
Edited version of frontal presentation or
final project.
Outline
A common generalization of counting problems are graph polynomials.
The most prominent of these are the matching polynomials,
the colouring polynomials and the Tutte polynomial.
For general graphs these are often hard to compute (#P hard).
There are also various multivariate generalizations
of these polynomials.
The aim of the course is to study some of the more prominent
graph polynomials such as
- Chromatic polynomial,
- Characteristic polynomial,
- Matching polynomial,
- Tutte polynomial
and some more recently introduced graph polynomials,
and to develop a general theory of
graph polynomials.
Studying graph polynomials is a fascinating topic combining
graph theory, combinatorics, algebra and complexity theory,
and has applications beyond mathematics, in computer science, physics, chemistry
and biology.
The course is part of a larger research project,
the
graph polynomial project, where we work on a Catalogoue of graph polynomials:
-
Catalogue of Graph polynomials (version November 2010)
-
Catalogue of Graph polynomials (version April 2011)
and is
suitable for students looking for MSc and PhD topics.
Literature
- N. Biggs, Algebraic Graph Theory, Cambridge University Press
1973 (1993)
- F. Dong, K. Koh and K. Teo, Chromatic Polynomials and
chromaticity of graphs, World Scientific 2005
-
C. Godsil and G. Royle, Algebraic Graph Theory, Springer 2001
-
D. Welsh, Complexity: Knots, colourings and counting,
London Mathematical Society Lecture Note Series, vol. 186, 1993
- B. Bollobas, Modern Graph Theory, Springer 1998
- R. Diestel, Graph Theory, Springer 1997
- D. Cvetkovic, P. Rowlinson and S. Simic,
An introduction to the theory of graph spectra, London Mathematical Society,
Student Texts vol. 75, 2010
- original papers